package str;

import javax.naming.InterruptedNamingException;

public class Bm {

    private static final int size=256;

    /**
     *
     * @param b 模式串
     * @param m 模式串长度
     * @param bc 散列表
     */
    private void generateBC(char[] b,int m,int[] bc){
        //初始化BC
        for (int i = 0; i < bc.length; i++) {
            bc[i]=-1;
        }
        for (int i = 0; i <m ; i++) {
            int ascii=(int)b[i];
            bc[ascii]=i;
        }
    }

    /***
     *
     * @param a  主串
     * @param n 主串长度
     * @param b 模式串
     * @param m 模式串长度
     * @return
     */
    public int bm(char[] a, int n,char[] b,int m){
        int[] bc =new int[size];//记录模式串中每个字符最后出现的位置
        generateBC(b,m,bc);
        int i =0; //对其的第一个字符
        while (i <= n-m){
            int j;
            for (j = m-1; j >=0 ; j--) {//从后向前匹配
                if(a[i+j]!=b[j]);break;//坏字符对应的下标是j
            }
            if(j<0){
                return i;//返回主串匹配成功的字符位置
            }
            // 这里等同于将模式串往后滑动j-bc[(int)a[i+j]]位
            i = i + (j - bc[(int)a[i+j]]);
        }
        return -1;
    }

    public static void main(String[] args) {

    }
}
